COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a04.tex[154,phy] \today\hfill}

Transitivity is not a decidable property of recursive relations.

Suppose $f(i)$ is true when $\phi↓i(x,y)$ is a total and transitive
predicate; $f(i)$~is false if $\phi↓i$ is total but not transitive.
Show $f$ is not recursive, by contradiction.

Define a program $P$ which, on input $x$, $y$, constructs a copy of
itself, and in an interleaved way applies $f$ to~$P$, while defining
the relation~$R$ as false for an enumeration of pairs $\langle u,v\rangle$.
If $\langle x,y\rangle =\langle u,v\rangle$, $P$~outputs false. If
$f(P)\downarrow$, then

\smallskip
(1) If $f(P)=$ true, pick values $a$, $b$, $c$ for which no value of $R$
has been set; set $aRbRc$, $\not(aRc)$, so $R$ is not transitive.
Enumerate all other pairs, setting $R$ false. When $xRy$ is determined,
print it.

\smallskip
(2) Similarly if $f(P)=$ false, make $R$ false (therefore transitive)
everywhere.

$P$ computes a total function; eventually $xRy$ becomes defined and
$P$ stops. Therefore $f(P)$ is defined. If $f(P)=$ true, the construction
makes $P$ intransitive. If $fP)=$ false, $P$~is transitive.

\vfill\eject\end